Graph

흔히 잘 알고 있는 Nodes & Edges로 이루어진 구조 $G = (V, E)$ G는 그래프, V는 정점의 집합, E는 간선의 집합

$$\begin{array}{c|ccccc} & A & B & C & D & E \\ \hline A & 0 & 1 & 0 & 0 & 1 \\ B & 1 & 0 & 1 & 1 & 1 \\ C & 0 & 1 & 0 & 1 & 0 \\ D & 0 & 1 & 1 & 0 & 1 \\ E & 1 & 1 & 0 & 1 & 0 \\ \end{array}$$

위에 그래프와 인접 행렬(Adjacency Matrix)를 보면 아래와 같은 특징을 알 수 있음 Undirected graph : 방향이 없는 그래프 즉, 0->1 이면 1->0 도 존재함 Identical Nodes -> Unweighted graph : 모든 관계가 동일한 중요도를 가짐

Homogeneous Graph & Heterogeneous Graph

Homogeneous Graph : 모든 노드와 엣지가 동일한 타입을 가짐 Heterogeneous Graph : 노드와 엣지가 다양한 타입을 가짐

책에서는 채용 네트워크 예시로 설명..

Bipartite Graph

이종 그래프의 한 종류로, 두 개의 노드 타입으로 이루어진 그래프 구직자 노드끼리, 채용 공고 노드끼리의 연결은 없고, 오직 구직자와 채용 공고 간의 연결만 존재

Cyclic Graph & Acyclic Graph & Directed Acyclic Graph

Cyclic Graph : 사이클(순환 구조)을 포함하는 그래프 Acyclic Graph : 사이클이 없는 그래프 Directed Acyclic Graph(DAG) : 방향성이 있는 비순환 그래프

Knowledge Graph

지식 그래프는 현실 세계의 개체(Entity)와 그들 간의 관계(Relationship)를 그래프 구조로 표현한 것 노드(Node)는 개체를 나타내고, 엣지(Edge)는 개체들 간의 관계를 나타냄 지식 그래프는 주로 정보 검색, 추천 시스템, 자연어 처리 등 다양한 분야에서 활용됨

Hypergraph

하이퍼그래프는 일반적인 그래프와 달리, 하나의 엣지가 여러 노드를 연결할 수 있는 그래프 구조 즉, 하나의 하이퍼엣지가 두 개 이상의 노드를 연결할 수 있음 하이퍼그래프는 복잡한 관계를 모델링하는 데 유용하며, 소셜 네트워크 분석, 생물학, 데이터 마이닝 등 다양한 분야에서 활용됨

Graph-Based learning

Node2Vec, DeepWalk : Random Walk 기반의 임베딩 기법 가장 유명한 그래프 기반 알고리즘 : PageRank

What is GNN?

Graph Neural Network(GNN)은 그래프 구조 데이터를 처리하고 학습하기 위한 딥러닝 모델의 한 종류 그림 : GNN의 작동방식 개요

ML을 그래프. 데이터 구조에 적용하는 것은 어려웠음, 그래프 데이터가 격자와 같은 형식과 데이터 구조로 표현될 때, 다량의 데이터 반복으로 이어질 수 있기 때문 -> 이게 뭔말인지 설명 ML은 그래프 표현의 순서에 영향을 받지 않음 -> 인접 행렬의 행과 열을 섞을 수 있다.

이를 해결하기 위해 그래프 기반 학습은 순열 불변(permutation invariant) 및 국소적 수용 영역(local receptive fields) 개념을 도입 순열 불변성 : 그래프의 노드 순서가 바뀌어도 결과에 영향을 미치지 않음 국소적 수용 영역 : 각 노드가 자신의 이웃 노드들로부터 정보를 수집하여 학습 GNN은 이러한 개념을 활용하여 그래프 구조 데이터를 효과적으로 처리하고 학습 GNN의 주요 구성 요소는 다음과 같음 메시지 전달(Message Passing) : 각 노드가 이웃 노드들로부터 정보를 수집하는 과정 노드 업데이트(Node Update) : 수집된 정보를 바탕으로 각 노드의 상태를 업데이트하는 과정 읽기(Readout) : 그래프 전체 또는 특정 노드의 표현을 추출하는 과정

순열 불변성(permutation invariant)란? [링크]

GNN은 이미지나 표와 같은 다른 데이터에는 적합하지 않음! 이미지와 표는 순열 불변이 아니기에 -> 이미지의 행과 열을 섞으면 당연히 다른 이미지가 나오고 표도 마찬가지

이미지 ML : 병진 불변성(translational invariance)이라는 개념이 적용됨 병진 불변성 : 이미지의 위치가 바뀌어도 동일한 특징을 인식할 수 있음

표 형식 vs 그래프 형식

타이타닉 데이터셋을 예시로 표 형식과 그래프 형식의 차이를 설명 실제로 재구성된 그래프 예시 그림 타이타닉 데이터 세트를 그래프로 변환하려면 승객 간의 기본 관계를 노드와 엣지로 표현하는 방법을 고려해야 합니다.

노드 — 그래프에서 각 승객은 노드로 표현될 수 있습니다. 객실, 가족 또는 "3등석 승객"과 같은 그룹과 같은 다른 개체에 대해서도 노드를 추가할 수 있습니다. 에지 - 에지는 이러한 노드 간의 관계 또는 연결을 나타냅니다. 예: 이용 가능한 데이터를 기준으로 가족(형제자매, 배우자, 부모 또는 자녀)인 승객 객실을 공유하거나 함께 여행하는 승객 공유 티켓 번호, 성 또는 기타 식별 기능에서 추론할 수 있는 사회적 또는 비즈니스 관계 이 그래프를 구성하려면 표의 기존 정보를 활용하고, 경우에 따라 2차 데이터 소스나 가정(예: 성을 연결하여 가족 그룹 생성)을 통해 정보를 보강해야 합니다. 이 과정을 통해 표 형식 데이터는 그림 1.9와 같이 그래프 기반 구조로 변환되며, 각 간선과 노드는 의미 있는 관계형 데이터를 캡슐화합니다

그래프 데이터가 깊이와 의미를 더하는 방식 데이터 세트를 그래프로 표현하면 승객 간의 사회적, 가족적 관계에 대한 훨씬 더 심층적인 시각을 제공합니다. 예를 들면 다음과 같습니다.

가족 관계 - 그래프는 특정 승객들의 관계(예: 부모, 자녀, 형제자매)를 명확하게 보여줍니다. 이는 가족 구성원들이 위기 상황에서 혼자 여행하는 사람들과 다른 행동을 보였을 가능성을 고려하여 생존 패턴을 이해하는 데 도움이 될 수 있습니다. 소셜 네트워크 - 가족을 넘어 그래프는 더 광범위한 소셜 네트워크(예: 우정이나 사업적 관계)를 보여줄 수 있으며, 이는 행동과 결과를 분석하는 데 중요한 요소가 될 수 있습니다. 커뮤니티 통찰력 - 그래프 구조를 통해 커뮤니티 감지 알고리즘을 통해 관련 또는 연결된 승객 클러스터를 식별할 수 있으며, 이를 통해 생존율, 구조 패턴 또는 기타 행동에 대한 새로운 통찰력을 얻을 수 있습니다

그래프 표현은 표 형식에서 명확하게 드러나지 않는 연관성을 보여 줄 수 있음!!

GNN Applications

Pinterest의 핀 추천 시스템

유사한 이분 그래프 예시 그림 핀과 보드는 두 가지 유형의 노드 Pinterest는 GNN을 활용하여 사용자에게 맞춤형 핀 추천 시스템을 구현 사용자와 핀 간의 상호작용을 그래프로 모델링하여, 사용자의 관심사에 맞는 핀을 추천 GCN(Graph Convolutional Network) PinSage -> 참고 [추후 링크]

Drug Discovery & Molecular Science

분자 구조의 그래프 예시 그림 분자는 원자(노드)와 화학 결합(엣지)으로 이루어진 그래프로 표현될 수 있음 GNN은 분자의 특성을 예측하고, 새로운 약물 후보를 발견하는 데 활용 분자 그래프의 구조적 특성을 학습하여, 약물의 효능과 부작용을 예측하는 모델 개발

신약 개발은 그래프 에측 문제로 이해 가능 독성이나 치료 효과와 같은 속성을 예측 discriminative model 신약 후보 물질 생성 generative model

대표적으로 VGAEs(Variational Graph Auto-Encoders) -> 참고 [추후 링크]

Mechanical reasoning

우리는 공이 떨어지면 어디에 떨어질지 직관을 통해 알 수 있지만, 기계는 아님.

자율주행 시스템, 제조, 로봇 공학 등 다양한 분야에서 기계가 물리적 환경을 이해하고 예측하는 능력이 중요 원래는 CV에 영역이였으나, 최근에 GNN을 활용하기 시작 Sanchez-Gonzalez et al.(2018)의 연구에서는 GNN을 사용하여 물리적 시스템의 동작을 모델링하고 예측하는 방법을 제안 그림 1.13에서 물체를 "기계적" 그래프로 생각할 수 있는 예를 보여줍니다. 이러한 물리적 추론 시스템의 입력 그래프는 문제를 반영하는 요소를 가지고 있습니다. 예를 들어, 사람이나 동물의 신체에 대해 추론할 때, 그래프는 신체의 팔다리가 연결되는 지점을 나타내는 노드로 구성될 수 있습니다. 자유 물체 시스템의 경우, 그래프의 노드는 튀는 공과 같은 개별 물체일 수 있습니다. 그래프의 모서리는 노드 간의 물리적 관계(예: 중력, 탄성 스프링 또는 강체 연결)를 나타냅니다. 이러한 입력을 통해 GNN은 물리적/기계적 법칙을 명시적으로 적용하지 않고도 물체 집합의 미래 상태를 예측하는 방법을 학습합니다[13]. 이러한 방법은 모서리 예측 의 한 형태입니다 . 즉, 시간 경과에 따라 노드가 어떻게 연결되는지 예측합니다. 또한, 이러한 모델은 시스템의 시간적 변화를 설명하기 위해 동적이어야 합니다. 이러한 문제는 6장에서 자세히 다룹니다.

When to use GNN?

기본적으로 3가지 기준

1. implicit relationships and interdependencies

데이터세트의 엔티티 간에 명시적으로 정의되지 않은 관계가 존재할 때 -> 찾아봐라 예를 들어, 소셜 네트워크에서 친구 추천 시스템은 사용자가 명시적으로 연결되지 않은 경우에도 잠재적인 관계를 식별해야 할 수 있음 또는, 고객행동분석에서 고객 간의 상호작용이 명시적으로 기록되지 않은 경우에도, GNN은 이러한 암묵적인 관계를 학습하여 더 나은 예측을 할 수 있음 투자 시장, 문서 및 텍스트 데이터에서 문서가 서로 인용, 공통 주제 또는 저자를 공유 등등

2. high dimensionality and sparsity

GNN에 적합한 고차원의 희소 데이터를 포함하는지 확인 -> 데이터셋에 직접적인 상호작용이나 관계가 제한적인 여러 개체가 포함되어 있는지 고려 예를 들어, 추천 시스템에서 사용자-아이템 상호작용 데이터(예: 구매 기록, 평가 등)는 일반적으로 희소하며, GNN은 이러한 희소한 상호작용을 통해 사용자와 아이템 간의 관계를 학습할 수 있음 신약 개발 분야에서도, 분자 간의 상호작용 데이터가 희소할 수 있으며, GNN은 이러한 희소한 데이터를 활용하여 분자의 특성을 예측하고 새로운 약물 후보를 발견하는 데 도움을 줄 수 있음

3. complex nonlocal interactions

데이터 세트에서 멀리 떨어진 요소들이 서로 어떻게 영향을 미치는가? GNN은 이러한 복잡한 비국소 상호작용을 모델링하는 데 효과적일 수 있음 예를 들어, 교통 네트워크에서 한 지역의 교통 상황이 다른 지역에 영향을 미칠 수 있으며, GNN은 이러한 비국소 상호작용을 학습하여 교통 흐름을 예측할 수 있음 또한, 생물학적 네트워크에서 멀리 떨어진 유전자나 단백질 간의 상호작용이 중요한 역할을 할 수 있으며, GNN은 이러한 복잡한 상호작용을 모델링하여 생물학적 기능을 이해하는 데 도움을 줄 수 있음

GNN이 적합한가? 질문

내 데이터에 모델링할 수 있는 암묵적 관계나 상호의존성이 있습니까? 개체 간의 상호작용이 직접적인 연결을 넘어서는 복잡하고 비국소적인 종속성을 보입니까? 데이터가 고차원이고 희소하며, 기본적인 관계 구조를 포착할 필요가 있습니까?

하나라도 "예"라고 대답하면 GNN이 적합할 수 있음

GNN 작동 방식

그림통해서 끝 Mental Model : GNN을 머신 러닝 문제에 적용하는 핵심 작업 흐름

첫 번째 단계는 원시 데이터를 그래프 형식으로 변환하는 것 -> 데이터에서 어떤 개체를 노드와 엣지로, 각 개체에 어떤 특성을 할당할지, 그래프 DB, 처리 시스템 등 데이터 저장 방식 결정 머신 러닝을 위해서는 학습 및 추론을 위해 데이터를 Preprocessing(Sampling, Batching...) -> 데이터를 학습,검증,테스트 세트

PyG(PyTorch Geometric), DGL(Deep Graph Library)과 같은 그래프 처리 라이브러리를 사용하여 그래프 데이터를 효율적으로 처리하고 모델을 구축 [!추후 링크]

GNN 모델의 고유한 메커니즘

모두 순열 불변(Permutation Invariant) 방식으로 그래프 데이터를 처리한다는 동일한 문제를 해결. 즉, 학습 과정에서 그래프 구조 전반에 걸쳐 정보를 인코딩하고 교환.

대부분의 다른 딥러닝 모델을 훈련하는 것과 유사한 프로세스를 따름

Message Passing

GNN의 핵심 메커니즘 중 하나는 메시지 전달(Message Passing)입니다. 각 노드는 자신의 이웃 노드들로부터 정보를 수집하고, 이를 바탕으로 자신의 상태를 업데이트합니다. 이 과정은 여러 번 반복되며, 이를 통해 노드들은 그래프 전체의 구조적 정보를 학습하게 됩니다.

그림 -> 메세지 전달 게층의 구성 요소 : 집계, 변환, 업데이트 단계

과정 : 입력(각 노드와 간선은 고유 특성) -> 각 노드는 인접한 이웃 노드들로부터 정보를 수집 = 메세지 -> 집계(aggregation) -> 변환(transformation) -> 업데이트(update) -> 출력(업데이트된 노드 특성) GNN의 각 메시지 전달 계층은 노드가 그래프에서 더 멀리 떨어져 있거나 더 많은 "홉"[!참고링크]을 거쳐 떨어진 노드로 부터 정보를 수집할 수 있도록 함께